//
// Created by lwj12 on 24-7-21.
//
#include"Heap.h"

void HPInit(Heap* php)
{
    assert(php);
    php->capacity = php->sz = 0;
    php->h = NULL;
}

void HPDestroy(Heap* php)
{
    assert(php);
    free(php->h);
    php->capacity = php->sz = 0;
    php->h = NULL;
}

void Swap(DataType* h1, DataType* h2)
{
    DataType tmp = *h1;
    *h1 = *h2;
    *h2 = tmp;
}

void AdjustUp(DataType* ps, size_t child)
{
    size_t father = (child - 1) / 2;
    while (child > 0)
    {
        if(ps[child] < ps[father])
        {
            Swap(&ps[child], &ps[father]);
            child = father;
            father = (child - 1) / 2;
        }
        else break;;
    }
}

void AdjustDown(DataType* ps, size_t sz, size_t father)
{
    size_t child = father * 2 + 1;
    while (child < sz)
    {
        if (child + 1 < sz && ps[child] > ps[child + 1]) child++;
        if (ps[father] > ps[child])
        {
            Swap(&ps[father], &ps[child]);
            father = child;
            child = father * 2 + 1;
        }
        else break;;
    }
}

void HPPush(Heap* php, DataType val)
{
    assert(php);
    if(php->capacity == php->sz)
    {
        size_t newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
        DataType* tmp = (DataType*)realloc(php->h, newCapacity * sizeof(DataType));
        if(tmp == NULL)
        {
            perror("realloc fail");
            return;
        }
        php->h = tmp;
        php->capacity = newCapacity;
    }
    php->h[php->sz++] = val;
    AdjustUp(php->h, php->sz - 1);
}

void HPPop(Heap* php)
{
    assert(php);
    assert(php->sz);
    Swap(&php->h[0], &php->h[php->sz - 1]);
    php->sz--;
    AdjustDown(php->h, php->sz, 0);
}

DataType HPTop(Heap* php)
{
    assert(php);
    return php->h[0];
}

bool HPEmpty(Heap* php)
{
    assert(php);
    return php->sz == 0;
}